本系列文章主要参考《算法导论》一书与《算法设计与分析》课件，暂定大纲：

算法基础

渐近记号、递归式求解
搜索算法

二分搜索、BFS、DFS
排序算法

交换排序、插入排序、选择排序、归并排序、以及非比较排序
分治策略

最大子数组问题、逆序计数、多项式乘法
动态规划

0-1背包、钢条切割
贪心算法

哈弗曼编码、
数据结构

栈、队、堆、树
图算法

拓扑排序、最短路径、最小生成树、关键路径
NP问题

P、NP、NPC

算法基础

0x00 算法基础

1. Asymptotic Notations （渐近记号）

Big-Oh

Asymptotic upper bound（渐进上界）

【定义】$f(n) = O(g(n))$ ：存在常量 $c$ 和 $n_0$ 使得对于任意的 $n \geq n_0$ 有 $f(n) \leq c·g(n)$ 。

【示例】

Big-Omega

Asymptotic lower bound（渐进下界）

【定义】$f(n) = \Omega(g(n))$ ：存在常量 $c$ 和 $n_0$ 使得对于任意的 $n \geq n_0$ 有 $f(n) \geq c·g(n)$ 。

【Equivalent definition】 $\lim_{n\rightarrow+\infty} \frac{T(n)}{f(n)} < \infty$

Big-Theta

Asymptotic tight bound（渐进紧确界）

【定义】$f(n) = \Theta(g(n))$ ：$f(n) = O(g(n)) \ and \ f(n) = \Omega(g(n))$

【Equivalent definition】 $\lim_{n\rightarrow+\infty} \frac{T(n)}{f(n)} > 0$

2. Solving Recurrences （递归式求解）

求解递归式，《算法导论》上给出了三种方法，但通常来讲，递归树法和主方法往往更加有效。

Recursion-tree Method （递归树法）

【定义】在递归树中，每一个结点表示一个单一问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。

【示例】

Substitution Method （代入法/替代法）

【示例】

Master Method and Master Theorem (主方法)

在分析递归的算法时，主方法可以较快的计算出算法的时间复杂度。

【主定理】 令 $a \geq 1$ 和 $b > 1$ 是常数， $f(n) = O(n^d)$ ，$T(n)$ 是定义在非负整数上的递归式： $$T(n) = aT(n/b)+f(n)$$

其中，我们将 $n/b$ 解释为 $T(\lfloor n/b \rfloor)$ 或 $T(\lceil n/b\rceil)$ ，这并不会影响递归式的渐进性质。

我们有， $$T(n)= \begin{cases} O(n^d)& \text{d > $log_ba$}\ O(n^d log_n)& \text{d = $log_ba$} \ O(n^{log_ba})& \text{d < $log_ba$} \end{cases}$$

对于三种情况的每一种，我们将 $f(n)$ 与 $n^{log_ba}$ 进行比较。直觉上，两个函数的较大者决定了递归式的解。

若函数 $f(n)$ 更大，如情况1，则解为 $T(n)=\Theta(n^{d})$ ；
若函数 $n^{log_ba}$ 更大，如情况3，则解为 $T(n)=\Theta(n^{log_ba})$ ；
若两个函数大小相当，如情况2，则乘上一个对数因子，解为 $T(n)=\Theta(n^{d}·logn)$ 。

主方法描述的算法，将原本规模为 $n$ 的问题，分解为 $a$ 个规模为 $n/b$ 的子问题，其中 $a, b \in \mathbb{Z^+}$ ，函数 $f(n)$ 包含了问题分解和子问题合并的代价。

递归树高度为 $log_bn$ ；
第 $k$ 层由 $a^k$ 个子问题构成，每个子问题的大小为 $n/b^k$ ；
因此，时间复杂度为 $a^k \times O(\frac{n}{b^k})^d = O(n^d) \times (\frac{a}{b^d})^k$ 。

【示例】

0x01 搜索算法

1. 二分搜索（BS）

二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 $O(logN)$ 。

【伪代码】

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (nums[m] == key) {
            return m;
        } else if (key < nums[m]) {
            h = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

【注意】

有两种计算中值 m 的方式：

m = (l + h) / 2
m = l + (h - l) / 2

l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算方法。

【变式】

二分思想很简单，但细节真的是魔鬼…

当使用二分查找的思想解决问题时，需仔细分析两点：

如何确定index在左子区间还是右？
跳出循环的条件？应返回什么？

2. 深度优先搜索（DFS）

深度优先搜索（Depth First Search）在碰到岔道口时，总是选择其中一条岔路前进，在岔路上如果又遇到新的岔道口，仍然选择新岔道口的其中一条岔路前进，直到碰到死胡同才回退到最近的岔道口选择另一条岔路。

由此可知，DFS是一种枚举所有完整路径以遍历所有情况的搜索方法，使用递归可以很好地实现深度优先搜索，基本模板如下：

void DFS(int x,int y)
{
    if(满足所需要的条件) {  
        相应的操作；return；
    } else {
    	for(int i= ; ;) { //如果是方向的话，会枚举方向
            枚举加方向的新坐标；
                if(界限 ：例如：不能出到地图外，有障碍，已经访问过) continue;
            设置已经访问新坐标；
                DFS(新坐标); 
            恢复到未被访问；
        }
    }
}

全排列

#include<cstdio>
 
using namespace std;
 
int n;
int visited[17] = {0};
int num[17] = {0};
 
 
void dfs(int k) {
    if(k > n) {
        for(int i = 1; i <= n; i++) {
            printf("%d ", num[i]);
        }
        printf("\n");
    }
     
    for(int i = 1; i <= n; i++) {
        if(!visited[i]) {
            visited[i] = 1;
            num[k] = i;
            dfs(k + 1);
            visited[i] = 0; 
        }
    }
    return ;
} 
 
int main() 
{
    scanf("%d", &n);
    dfs(1);
         
    return 0;
}

组合数

#include<cstdio>
#include<vector>

using namespace std;

int n, r;
vector<int> ans;

void dfs(int k) {
	// 剪枝：ans 长度加上区间 [k, n] 的长度小于 r，不可能构造出长度为 r 的 ans
    if (ans.size() + (n - k + 1) < r) {
        return;
    }

	if(ans.size() == r) {
		for(int i = 0; i < r; i++) {
			printf("%d ", ans[i]);
		}
		printf("\n");
		return ;
	}
	
	if(k > n) {
		return ;
	} 
	// 选择k
	ans.push_back(k);
	dfs(k + 1);
	ans.pop_back();
	// 不选k
	dfs(k + 1);
	
	return ;
} 


int main() 
{
	scanf("%d %d", &n, &r);
	dfs(1);
		
	return 0;
}

3. 广度优先搜索（BFS）

广度优先搜索（Breadth First Search）在碰到岔道口时，总是先依次访问从该岔道口能直接到达的所有结点，然后再按这些节点被访问的顺序去依次访问它们能直接到达的所有结点，以此类推，直到所有结点都被访问为止。

BFS一般由队列实现，且总是按层次的顺序进行遍历，其基本写法如下：

void BFS(int s) {
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        // 取出队首元素 top；
        // 访问队首元素 top；
        // 将队首元素出队；
        // 将top的下一层结点中未曾入队的结点全部入队，并设置为已入队；
    }
}

求“块”的个数

给出一个 mxn 矩阵，矩阵中的元素为0或1。称位置（x, y）与其赏析左右四个位置 (x, y+1)、(x, y-1)、(x+1, y)、(x-1, y) 是相邻的。如果矩阵中有若干个1是相邻的，那么称这些1构成了一个“块”。求给定的矩阵中“块的个数”。

【示例】

例如下面的 6x7 矩阵中，“块的个数”为4。

0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0 
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

【基本思想】

枚举每一个位置的元素：

如果为0，则跳过；
如果为1，则使用BFS查询与该位置相邻的4个位置，判断它们是否为1。
- 如果某个相邻的位置为1，则同样去查询与该位置相邻的4个位置，直到整个“1”块访问完毕
- 同时为了防止走回头路，一般可以设置一个bool型数组 inq （即 in queue）来记录每个位置是否已入过队。

一个小技巧是，对当前位置 (x, y) 来说，不妨设置下面两个增量数组，来表示四个方向。

1
2
3

// 竖着看即为 (0, 1), (0, -1), (1, 0), (-1, 0)
int X[] = {0,  0, 1, -1};
int Y[] = {1, -1, 0,  0};

这样就可以使用for循环来枚举四个方向：

for(int i = 0; i < 4; i++) {
    newX = nowX + X[i];
    newY = nowY + Y[i];
}

本题的核心代码如下：

#include<cstdio>
#include<queue>
using namespace std;

const int maxn = 100;
typedef struct _node {
    int x, y;
} Node;

int n, m;	// 矩阵大小 n*m
int matrix[maxn][maxn];		// 01矩阵
bool inq[maxn][maxn];		// 记录位置是否已访问过
int X[] = {0,  0, 1, -1};
int Y[] = {1, -1, 0,  0};

bool judge(int x, int y) {
    // 越界，返回false
    if(x >= n || x < 0 || y >= m || y < 0)	return false;
    // 当前位置为0，或 (x, y)已访问过，返回false
    if(matrix[x][y] == 0 || inq[x][y] == true)	return false;
    // 以上都不满足，返回true
    return true;
}

// BFS 访问位置 (x, y) 所在的块
void bfs(int x, int y) {
    queue<Node> Q;
    Node cur;
    cur.x = x, cur.y = y;
    Q.push(cur);		// 将当前节点入队
    inq[x][y] = true;	// 标记
    
    while(!Q.empty()) {
    	Node top = Q.front();	// 取队首元素
        Q.pop();
        // 循环4次，得到4个相邻位置
        for(int i = 0; i < 4; i++) {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if(judge(newX, newY)) {	// 如果新位置需要访问
                Node node;
                node.x = newX, node.y = newY;
                Q.push(node);
                inq[newX][newY] = true;
            }
        }
    }
}

0x02 排序算法

本章主要参考博客：十大经典排序算法（动图演示）

分类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 $O(nlogn)$，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
相关概念：
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

1. 交换排序

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。

【算法思想】

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的尾端。

它重复地扫描待排序数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
重复上述操作直到没有再需要交换，也就是说该数列已经排序完成。

【动图演示】

![](https://gitee.com/Jayyy1/images/raw/master/posts/Computer Science/Algorithm/BubbleSort.gif)

【伪代码】

for i in [0, len):			// 每一轮都将未排序序列中的一个最大的元素交换到已排序子序列的首部，重复len轮
	for j in [0, len-i-1):	// 0--未排序序列--(len-i)--已排序序列--len
		if(A[j] > A[j+1])：
			swap(A[j], A[j+1])

快速排序

快速排序（Quick Sort）是一个典型的分治算法，用于求解 Kth Element 问题，也就是第K个元素的问题。

【算法思想】

我们对数组 $a[l⋯r]$ 做快速排序的过程是（参考《算法导论》）：

分解：将数组 $a[l⋯r]$ 「划分」成两个子数组 $a[l⋯q−1]$ 、$a[q+1⋯r]$，使得 $a[l⋯q−1]$ 中的每个元素小于等于 $a[q]$，且 $a[q+1⋯r]$ 中的每个元素大于等于 $a[q]$ 。其中，计算下标 $q$ 也是「划分」过程的一部分。
解决：通过递归调用快速排序，对子数组 $a[l⋯q−1]$ 和 $a[q+1⋯r]$ 进行排序。
合并：因为子数组都是原址排序的，所以不需要进行合并操作，$a[l⋯r]$ 已经有序。

上文中提到的「划分」过程是：从子数组 $a[l⋯r]$ 中选择任意一个元素 $x$ 作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， $x$ 的最终位置就是 $q$ 。

由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 $x$ 的最终位置为 $q$ 。最终，经过平均 $logn$ 次的「划分」操作，得到排序后的数组。

【动图演示】

![](https://gitee.com/Jayyy1/images/raw/master/posts/Computer Science/Algorithm/QuickSort.gif)

【伪代码】

这里使用 $p$ 代替 $l$ 是因为latex下 $l$ 与 $1$ 容易混淆。

【改进版】

为了解决上述问题，加入random模块，能够尽可能使时间复杂度接近 $O(nlogn)$ 。

下面的 Randomized-Partition 有点小问题，最后返回的应该是 Partition(A, p, r) ，而非 j 。

2. 插入排序

简单插入排序

插入排序（Insertion-Sort）是一种简单直观的排序算法。

【算法思想】

每次在未排序序列中取一个数据，然后在已排序序列中从后向前扫描，通过比较找到相应位置并插入。

【动图演示】

![](https://gitee.com/Jayyy1/images/raw/master/posts/Computer Science/Algorithm/InsertionSort.gif)

【伪代码】

for i in [1, len):
	temp = A[i]
	for j in [i-1, 0]:		// 从后向前扫描有序子序列，找到第1个比temp小的元素，把temp插在它后面
		if(temp >= A[j]):
			break
		A[j+1] = A[j]
	A[j+1] = temp

希尔排序

希尔排序（Shell Sort）又叫缩小增量排序，是简单插入排序的改进版，第一个突破O(n2)的排序算法。

【算法思想】

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。

而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

简单来说，希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序（有点类似组相联映射，组间互不影响，组内直接插入）。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

【长图演示】

【伪代码】

for(int gap = len/2; gap > 0; gap /= 2) {
	// 按gap分好组后，多组交替执行
    for(int i = gap; i < len; i++) {
        // 对于当前A[i]的同组元素，即 i, i-gap, i-2*gap, ... 执行直接插入操作
        int j = i;
        int current = A[i];
        while(j - gap >= 0 && current < A[j - gap]) {
            A[j] = A[j - gap];	// 数组元素移动法
            j -= gap;
        }
        A[j] = current;
    }
}

3. 选择排序

简单选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。

【算法思想】

每次在未排序序列中选择一个最小的放在已排序序列的末尾。

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置;
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

【动图演示】

![](https://gitee.com/Jayyy1/images/raw/master/posts/Computer Science/Algorithm/SelectionSort.gif)

【伪代码】

for i in [0, len):
	minIndex = i
	for j in [i+1, len):	// 在未排序子序列中找到一个最小值，并交换到已排序序列的末尾
		if(A[j] < A[minIndex]):
			minIndex = j
	swap(A[i], A[minIndex])

堆排序

堆排序（Heap Sort）是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成，参考图解排序算法(三)之堆排序。

【算法思想】

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点；
将其与末尾元素进行交换，此时末尾就为最大值；
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值；
如此反复执行，便能得到一个有序序列了。

【动图演示】

![HeapSort](http://jayyy1.gitee.io/images/posts/Computer Science/Algorithm/HeapSort.gif)

【伪代码】

交换法：

// 对heap数组在[low, high]范围进行向下调整，下标从1开始
// 其中low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
void downAdjust(int low, int high) {
    int i = low, j = 2 * i;		// i为欲调整结点，j为其左孩子
    while(j <= high) {			// 存在孩子结点
    	// 如果右孩子存在，且右孩子的值大于左孩子
        if(j + 1 <= high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        // 如果孩子中最大的权值比欲调整节点i大
        if(heap[j] > heap[i]) {
            swap(heap[j], heap[i]);
            i = j;				// 保持i为欲调整节点、j为i的左孩子
            j = i * 2;
        } else {
            break;				// 孩子的权值均比欲调整节点i小，调整结束
        }
    }
}

// 建堆
void createHeap() {
    for(int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);
    }
}

// 堆排序
void heapSort() {
    createHeap();		// 建堆
    for(int i = n; i > 1; i--) {
        swap(heap[i], heap[1]);		// 交换heap[i]与堆顶
        downAdjust(1, i-1);			// 调整堆顶
    }
}

移动法：

// 下标从0开始
public static void heapSort(int[] arr){
    //1.构建大顶堆
    for(int i=arr.length/2-1; i >= 0; i--){
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(arr,i,arr.length);
    }
    //2.调整堆结构+交换堆顶元素与末尾元素
    for(int j=arr.length-1;j>0;j--){
        swap(arr,0,j);//将堆顶元素与末尾元素进行交换
        adjustHeap(arr,0,j);//重新对堆进行调整
    }
}
/**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
public static void adjustHeap(int[] arr,int i,int length){
    int temp = arr[i];	//先取出当前元素i
    for(int k=2*i+1; k < length; k=2*k+1) {		//从i结点的左子结点开始，也就是2i+1处开始
        if(k+1 < length && arr[k] < arr[k+1]) {	//如果左子结点小于右子结点，k指向右子结点
            k++;
        }
        if(arr[k] > temp){		//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i] = arr[k];
            i = k;	
        }else{					//如果子节点都小于父结点，说明已调整完毕
            break;
        }
    }
    arr[i] = temp;	//将temp值放到最终的位置
}

4. 归并排序

二路归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

【算法思想】

分解：把长度为n的输入序列分成两个长度为n/2的子序列；
解决：对这两个子序列分别采用归并排序；
合并：将两个排序好的子序列合并成一个最终的排序序列。

【动图演示】

【伪代码】

5. 非比较排序

在前面的排序中，各个元素的次序依赖于它们之间的比较，我们把这类排序算法称为比较排序。能够证明的是，任何比较排序在最坏情况下都要经过 $\Omega (nlogn)$ 次比较。

下面我们介绍三种非比较排序算法，可在线性时间内完成排序。

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，通过统计它们的个数进行排序。

作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

【算法思想】

找出待排序的数组中最大和最小的元素，并据此建立数组C；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1，直至为0，继续下一个。

【动图演示】

【伪代码】

int* countSort(int A[], int n) {
    // 1. 找出数组A中的最大值
    int max_val = MIN_VALUE;
    for(int i = 0; i < n; i++) {
        max_val = max(max_val, A[i]);
    }
    // 2. 计数数组C
    int *C = new int[max_val + 1];
    fill(C, C + max_val + 1, 0);
    for(auto num: A) {
        C[num]++;
    }
    // 3. 遍历计数数组，生成结果数组
    int *res = new int[n];
    int k = 0;
    for(int i = 0; i <= max_val; i++) {
        while(C[i]) {
            res[k++] = i;
            C[i]--;
        }
    }
    return res;
}

桶排序

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素。通过划分多个范围相同的区间，每个子区间自排序，最后合并。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

【算法思想】

通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

【长图演示】

【伪代码】

int* bucketSort(int A[], int n) {
    // 1. 计算最大值与最小值，并确定映射函数
    int minVal = MAX_VALUE;
    int maxVal = MIN_VALUE;
    for(int i = 0; i < n; i++) {
        minVal = min(minVal, A[i]);
        maxVal = max(maxVal, A[i]);
    }
    int bSize = n;	// 每个桶的大小
    int bNum = (maxVal - minVal) / bSize + 1;
    vector<vector<int>> buckets(bNum, vector<int>());	// 初始化桶
    // 2. 映射：把每个元素放入对应桶中
    for(auto num: A) {
        bNo = (num - minVal) / bSize;
        buckets[bNo].push_back(num);
    }
    // 3. 对每个桶进行排序，并合并
    int k = 0;
    for(int i = 0; i < bNum; i++) {
        vector<int> bucket = buckets[i];
        sort(bucket, bucket + bucket.size());
        for(int j = 0; j < bucket.size(); j++) {
            A[k++] = bucket[j];
        }
    }
    return A;
}

基数排序

基数排序的核心思想是，把每个元素看成由“位”组成的数，比如 123 就是由个位的3，十位的2和百位的1组成，然后按照从低位到高位的顺序进行排序。

【算法思想】

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）。

【动图演示】

【伪代码】

int* radixSort(int A[], int n) {
    // 1. 计算最大值，进而求得最大位数
    int maxVal = MIN_VALUE;
    for(int i = 0; i < n; i++) {
        maxVal = max(maxVal, A[i]);
    }
    int maxDigit = 0;
    while(maxVal) {
        maxVal /= 10;
        maxDigit++;
    }
    // 2. 生成radix数组并排序
    int mod = 10, dev = 1;
    for(int d = 0; d < maxDigit; d++, mod *= 10, dev *= 10) {	// 从低位到高位进行统计
      	// 初始化radix
        vector<vector<int>> radix(10, vector<int>());
        // 生成当前位置的radix数组
        for(int i = 0; i < n; i++) {
            int digit = (A[i] % mod) / dev;	// 取出当前位上的数字
            radix[digit].push_back(A[i]);	// digit: 0~9
        }
        // 根据当前位，重排数组A
        int k = 0;
        for(int i = 0; i < 10; i++) {
            vector<int> temp = radix[i];
            for(int j = 0; j < temp.size(); j++)	
                A[k++] = temp[j]; 
        }
    }
    return A;
}

算法设计

本章主要参考《算法导论》一书与《算法设计与分析》课件，大纲：

0x03 分治策略

分治策略（Divide-and-conquer (D&C)）的基本思想就是将一个规模为n的问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将子问题的解合并得到原问题的解。

分解（Divide）

Dividing a given problem into two or more subproblems(ideally of approximately equal size)
解决（Conquer）

Solving each subproblem (directly if small enough or recursively)
合并（Combine）

Combining the solutions of the subproblems into a global solution.

【典例】

MergeSort（归并排序）
QuickSort and Partition (快速排序与划分)
Maximum Contiguous Subarray (最大子数组)
Counting Inversions (逆序计数)
Polynomial Multiplication (多项式乘法)

1. 最大子数组问题

MCS - Maximum Contiguous Subarray Problem

问题定义

给定一个数组 $A[1…n]$ ，找到一个 $V(i,j) = \sum_{x=i}^j A(x)$ ，使得 $V(i,j)$ 最大。

蛮力枚举

计算每一对 $V(i,j)$ ，但注意到 $V(i,j) = \sum_{x=i}^j A(x) = V(i,j-1) + A[j]$ ，因此可以复用已计算过的数据，简化为 $O(n^2)$ 。

分而治之

分解：对于 $A[low…high]$ 的最大连续子数组 $A[i…j]$ 必是以下三种情况之一。

S1：完全位于左边 $A[low…mid]$ 中，因此 $low \leq i \leq j \leq mid$ ；

S2：完全位于右边 $A[mid+1…high]$ 中，因此 $mid < i \leq j \leq high$ ；

S3：跨越了中点，因此 $low \leq i \leq mid < j \leq high$ ；
解决：S1和S2可以递归解决，因此只需要寻找跨越中点的最大子数组。实际上，S3可以在线性时间内解决，从中点开始向左右寻找最大和即可。
合并：在三种情况中选取和最大者。

补：一种线性时间内的DP算法

也称为扫描算法：

53. Maximum Subarray (Easy) ，重点在于连续子数组，故主要是看前面的和。若大于0，则加上，否则，从当前开始重新计算和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty())    return 0;

        int preSum = nums[0];
        int maxSum = preSum;
        for(int i = 1; i < nums.size(); i++) {
            preSum = preSum > 0? preSum+nums[i] : nums[i];
            maxSum = max(maxSum, preSum);
        }
        return maxSum;
    }
};

2. 逆序计数

Counting Inversions

问题定义

逆序对：当 $i<j$ 时，$A[i] > A[j]$ 的二元组 $(A[i], A[j])$ 。

蛮力枚举

枚举所有 $(i,j)$ 并计数。

分而治之

分解：同MSC问题，考虑三种情况：

S1：仅在 $A[left…mid]$ 中的逆序对数目；

S2：仅在 $A[mid+1…right]$ 中的逆序对数目；

S3：跨越中间点的逆序对数目。
解决：S1和S2可递归求解，难点在于如何求解S3？
合并：S = S1 + S2 + S3。

【S3：排序求解】

算法思想：
- 分别对左右数组 $A[left…mid]$ 和 $A[mid+1…right]$ 进行排序；
- 对于每个 $A[j] \in A[mid+1…right]$ ，用二分查找为其在左数组 $A[left…mid]$ 中定位；
- $A[j]$ 在 $A[left…mid]$ 中定位点右侧的元素均可与 $A[j]$ 构成逆序对。
分析：
- 求解S3算法运行时间：$O(nlog_n)$ ；
- 分治框架的算法运行时间：$T(n)=2(n/2) + O(nlog_n)$ → $O(nlog_n^2)$ ；

这种算法在求解每个子问题时都需要进行一次排序过程，那么有没有进一步优化的可能？

【S3：归并求解】

尝试将排序过程融入整个算法框架，或者说，利用归并排序框架保证合并后数组的有序性，然后在归并过程的同时计算逆序对数目。

能这样做的原因是已经求得了S1与S2的逆序对数目，而S3只是求解跨越中间的逆序对数，必有 $i < j$ （$i$ 在左子数组中，$j$ 在右子数组中），因而左右子数组中元素的顺序并不影响S3的求解。

例如，A = [6 5 4 3 2 1]，6无论在左子数组的哪个位置，其逆序数一定是3，其余元素亦是如此。

从左到右扫描有序子数组：$left \leq i \leq mid, mid+1 \leq j \leq right$ 。
- 如果 $A[i] > A[j]$ ，统计逆序对的数目（$i…mid$ 均是 $j$ 的逆序对），$j$ 向右移；
- 如果 $A[i] \leq A[j]$ ，$i$ 向右移；

这样，整个算法复杂度为 $O(nlog_n)$ 。

3. 多项式乘法

Polynomial Multiplication

问题定义

给定 $A(x) = \sum_{i=0}^n a_ix^i$ ，$B(x) = \sum_{i=0}^m b_ix^i$ ，求解 $C(x) = A(x)B(x) = \sum_{k=0}^{n+m} c_kx^k$ 。

Input：$A[0…n]$ 、$B[0…m]$
Output：$C[0…n+m]$

蛮力枚举

两个loop即可，复杂度 $O(n^2)$ ，具体略。

分而治之

Obersvation1： $A \times B = (A_0,A_1x_{n/2}) \times (B_0,B_1x_{n/2}) = A_0B_0+ A_0B_1x_{n/2} + A_1B_0x_{n/2} + A_1B_1x_{n}$

由主定理，时间复杂度为 $O(n^2)$ 。

Obersvation2：用 $A_0B_0, A_0B_1+A_1B_0,A_1B_1$ 三项代替 $A_0B_0, A_0B_1, A_1B_0,A_1B_1$ 四项。
- $Y = (A_0+A_1)(B_0+B_1)$
- U = $A_0B_0$
- $Z=A_1B_1$
- $A_0B_1 + A_1B_0 = Y - U - Z$

由主定理，时间复杂度为 $O(n^{3/2})$ 。

0x04 动态规划

动态规划（Dynamic Programming）跟分治策略十分相似，都是通过组合子问题的解来求解原问题，不同在于：

动态规划解决：重叠子问题
分而治之解决：独立子问题

动态规划算法通常用来求解最优化问题（optimization problem），步骤如下：

刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自底向上的方法
利用计算出的信息构造一个最优解

1. 0-1 背包

0-1 Knapsack

问题定义

蛮力枚举：递归求解

$KnapsackSR(i, c)$ ：前 $i$ 个商品中，容量为 $c$ 时的最优解。

问题结构分析：

若背包容量为 $c$，对于第 $i$ 个商品有两种选择，取二者最大值：
- 选择 $i$：$KnapsackSR(i-1, c-v_i) + p_i$
- 不选 $i$：$KnapsackSR(i-1, c)$
递推关系建立：

$KnapsackSR(i,c) = max{KnapsackSR(i-1,c-v_i) + p_i,\ KnapsackSR(i-1,c)}$
伪代码：
复杂度分析：
优化：

记录子问题解，避免重复计算

自顶向下的带备忘录递归

算法思想：

构造备忘录 $P[i, c]$ ，表示在前 $i$ 个商品中选择，背包容量为 $c$ 时的最优解。

伪代码：

补充下面两行代码即可

if P[i,c] >= 0:
	return P[i,c]
...
P[i,c] = P

自底向上

自底向上版本采用子问题的自然顺序：若 $i < j$ ，则规模为 $i$ 的子问题比规模为 $j$ 的子问题“更小”。因此，依次求解规模为 $j=0,1,…,n$ 的子问题。

算法思想

构造追踪数组 $Rec[i,c]$ ，以便后面输出问题最优解。
伪代码

输出最优解方案

时间复杂度：$O(n·c)$

2. 钢条切割

Rod-Cutting

问题定义

蛮力枚举：递归求解

问题结构分析：

对于长度为n的钢条，可以切割成长度为 i 和 n-i 的两段，共有n种切割方案，取最大值
- 每种方案收益为：$p_i + r_{n-i}$
递推关系建立：

$r_n = max_{1 \leq i \leq n} (p_i + r_{n-i})$
伪代码：

CUT-ROD(p, n)：以价格数组 p[1…n] 和整数 n为输入，返回长度为n的钢条的最大收益。
1
2
3
4
5
6
if n == 0:
return 0
q = -INF
for i = 1 to n:
q = max(q, p[i] + CUT-ROD(p, n-i))
return q

自顶向下的带备忘录递归

算法思想：

构造备忘录 $r[n]$ ，记录长度为n的钢条的最大收益。

伪代码：

补充下面两行代码即可

if r[n] >= 0:
	return r[n]
...
r[n] = q

自底向上

算法思想

构造追踪数组 $rec[1…n]$ ：
- 切割：$rec[j] = i$ ，$i$ 为该切割方案中的钢条长度；
- 不切：$rec[j] = j$
伪代码

最优方案追踪

时间复杂度：$O(n^2)$

3. 矩阵链乘法

Chain Matrix Multiplication

问题定义

自底向上

问题结构分析：

对于矩阵链 $U_i…U_kU_{k+1}…U_j$ ，可以划分为 $(U_i…U_k) \times (U_{k+1}…U_j)$ ，其中 $i \leq k < j$ 。枚举所有可能位置 $i…j-1$ ，共 $j-i$ 种。
递推关系建立：

令 $D[i, j]$ 表示矩阵链 $U_{i…j}$ 所需标量乘法的最小次数，则 $D[i, j] = min_{i \leq k < j}(D[i,k] + D[k+1,j] + p_{i-1}p_kp_j)$ 。
自底向上计算：

【区间DP】
最优方案追踪：

4. 最长公共子序列

LCS - Longest Common Subsequences

问题定义

自底向上

问题结构分析：

记 $X_i$ 表示 $X$ 的第 $i$ 前缀，考虑末尾字符：
- 若 $x_n = y_m$ ，则 $z_l = x_n = y_m$ 且 $Z_{l-1}$ 是 $X_{n-1}$ 和 $Y_{m-1}$ 的一个 LCS；
- 若 $x_n \neq y_m$ ，那么 $z_l \neq x_n$ 就意味着 $Z$ 是 $X_{n-1}$ 和 $Y$ 的一个 LCS；
- 若 $x_n \neq y_m$ ，那么 $z_l \neq y_m$ 就意味着 $Z$ 是 $X$ 和 $Y_{m-1}$ 的一个 LCS；
递推关系建立：

令 $C[i,j]$ 表示 $X_i$ 和 $Y_j$ 的 LCS 的长度。

$$C[i, j] = \begin{cases} 0& \text{若 i = 0 或 j = 0}\ C[i-1,j-1] + 1& \text{若 i, j >0 且 $x_i$ = $y_j$}\ max(C[i,j-1], C[i-1,j])& \text{若 i, j >0 且 $x_i$ $\neq$ $y_j$} \end{cases}$$
自底向上计算：
最优方案追踪：

构造追踪数组 $rec[1..n]$

$$rec[i, j] = \begin{cases} LU& \text{若 C[i, j] = C[i-1, j-1]}\ U& \text{若 C[i, j] = C[i-1, j]}\ L& \text{若 C[i, j] = C[i, j-1]}\ \end{cases}$$

5. 最长公共子串

LCS - Longest Common Substring

问题定义

自底向上

问题结构分析：

类似于最长公共子序列，区别在于，最长公共子串是要求连续的。
递推关系建立：

$$C[i, j] = \begin{cases} 0& \text{$x_i$ $\neq$ $y_j$} \ C[i-1, j-1] + 1& \text{$x_i$ = $y_j$} \end{cases} $$
自底向上计算

最优方案追踪：

6. 最小编辑距离

MED - Minimum Edit Distance

问题定义

自底向上

问题结构分析：

$D[n,m]$：字符串 $s[1..n]$ 变为 $t[1..m]$ 的最小编辑距离。
递推关系建立：

考察末尾元素：
- 删除：$D[i,j] = D[i-1, j] + 1$
- 插入：$D[i,j] = D[i, j-1] + 1$
- 替换：$$D[i,j] = D[i-1, j-1] + \begin{cases} 0& \text{if s[i] = t[j]}\ 1& \text{if s[i] $\neq$ t[j]} \end{cases}$$
综合上面三种方式，取最小值。
自底向上计算：
- 初始化：
  
  $D[i, 0] = i$ ，把长度为 $i$ 的串变为空串至少需要 $i$ 次操作（删除）
  
  $D[0,j] = j$ ，把空串变为长度为 $j$ 的串至少需要 $j$ 次操作（插入）
- 递推公式：
  
  $$D[i,j] = min \begin{cases} D[i-1,j]+1& \text{删除}\ D[i,j-1]+1& \text{插入}\ D[i-1,j-1] + \begin{cases} 0,& \text{if s[i] = t[j]}\ 1,& \text{if s[i] $\neq$ t[j]} \end{cases} & \text{替换}\ \end{cases}$$
最优方案追踪：

伪代码：

输出最优方案：

时间复杂度：$O(mn)$

7. 所有结点对的最短路径

All-Pairs Shortest Paths

0x05 贪心算法

贪心选择性质：通过作出局部最优（贪心）选择来构造全局最优解。
最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最有子结构性质。

1. 部分背包问题

Fractional Knapsack Problem

问题定义

贪心策略

提出贪心策略：最高性价比优先
证明策略正确：略

时间复杂度：$O(nlogn)$

2. 活动选择问题

Activity Selection Problem

问题定义

贪心策略

正确策略：最早结束活动优先

伪代码：

时间复杂度：$O(nlogn)$

3. 哈夫曼编码

Huffman Coding Problem

前缀码：编码的任意前缀不是其他编码

问题定义

贪心策略

优先处理高频字符
- 结点左孩子固定为叶结点，非最优方案。
优先处理低频字符

时间复杂度：$O(nlogn)$

总结

动态规划：考察全局，求解子问题，组合最优解；
贪心策略：考察局部，直接做决策，构造最优解。

数据结构

0x06 基础数据结构

栈、队、树、堆

堆

（二叉）堆是一个数组，它可以被看成一个近似的完全二叉树，树上的每一个节点对应数组中的一个元素。

表示堆的数组 $A$ 包括两个属性：

$A.length$ 给出数组元素的个数；
$A.heap_size$ 表示有多少个堆元素存储在该数组中。

树的根节点是 $A[1]$ ，这样给定一个结点的下标 $i$ ，很容易得到它的父节点、左孩子和右孩子的下标：

$PARENT(i): \lfloor i/2 \rfloor$
$LEFT(i): 2i$
$RIGHT(i): 2i+1$

二叉堆可以分为两种形式，大顶堆和小顶堆。

大顶堆：$A[PARENT(i)] \geq A[i]$ ，堆中的最大元素存放在根结点中，且任意子树中所包含的结点的值都不大于该子树根结点的值。
小顶堆：$A[PARENT(i)] \leq A[i]$ ，正好相反。

在堆排序算法中，我们使用的是大顶堆，小顶堆通常用于构造优先队列。堆中的一些基本过程如下：

MAX-HEAPIFY 过程：维护最大堆性质，时间复杂度 $O(log_n)$

MAX-HEAPIFY(A, i)
    l = LEFT(i), r = RIGHT(i)
    largest = i
    if l <= A.heap_size and A[l] > A[largest]:
        largest = l
    if r <= A.heap_size and A[r] > A[largest]:
        largest = r

    if largest != i:
        swap(A[i], A[largest])
        MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP 过程：从无序的输入数组中构造一个大顶堆，时间复杂度 $O(nlog_n)$ 。

BUILD-MAX-HEAP(A)
    A.heap_size = A.length
    for i in [n/2, 1]:
        MAX-HEAPIFY(A, i)

HEAPSORT 过程：对一个数组进行原址排序，时间复杂度 $O(nlog_n)$ 。

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i in [n, 2]:
    	swap(A[1], A[i])
    	A.heap_size--
    	MAX-HEAPIFY(A, 1)